package Recursion_05;

/*
 * @Author 罗
 * @date 2020/3/15 - 6:00 下午
 *
 */

import org.junit.Test;

import java.util.Arrays;

public class EightQueens {
    /*
    * 用于存放放置八个皇后的行、列坐标
    * 可以用一纬数组来表示二维坐标
    * 下标n代表行号
    * 下标对应的数组的值map[n]为皇后的列标
    * */
    static int[] map;
    static {
        map = new int[8];
        for (int i = 0; i < map.length; i++) {
            map[i] = -1;
        }
    }



    @Test
    public void test(){

            findWay(0);

    }

    /**
     * 八皇后问题算法思路分析
     * (1)第一个皇后先放在第一行第一列
     * (2)第二个皇后放在第二行第一列，然后判断是否成立（不和之前的任一皇后在同一列，或同一斜线）
     *      如果不成立，则继续放在第二列第三列，依次把所有列都放完，找到一个合适
     * (3)继续放置第三个皇后在第三行，还是在第一列，第二列..直到第8个皇后也能放在一个不冲突的位置
     *      算是得到了一个正确解
     * (4)当得到一个真确解时，在栈回退到上一个栈时，就会开始回溯，
     *      即将第一个皇后，放到第一列的所有正确解，全部得到
     * (5)然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4步骤
     * 0:未放置过皇后
     * 2:已经放置了皇后
     * 3:已经尝试过放置皇后，并且会失败
     * @param i 寻找第i行的皇后
     * @return
     * 0 4 7 5 2 6 1 3
     */

    static int count = 0;
    public static void findWay(int i){
//        第八个皇后的位置已经确定
        if(i == 8){
//            printQueens();
            System.out.println(count+++"\t"+Arrays.toString(map));
            return;
        }else{
                /*
                 * 顺序测试本行，皇后能摆放的位置
                 *      依次放入皇后，并判断是否冲突
                 * */
                for (int k = 1; k < 9; k++) {
//                  将第i行皇后所在的列写入一维数组
                    map[i] = k;

//                    如果皇后能够放在这一列
                    if(judge(i)){
//                        进入第n+1行的测试
//                        放入第n+1个皇后，即开始递归
                        findWay(i+1);
                          /*
                                每一次递归时，进入到findWay()都有 for (int k = 1; k < 9; k++) 都有回溯
                                当(i==8)第8个皇后已放置好，得出结果并打印
                                每次回溯完，都将继续寻找本行的下一列，从第八个皇后回退到第7个皇后，然后将第7个皇后移动到下一列
                                寻找当前6个皇后都已经固定的情况下，第七个皇后能摆放的第二个位置，然后再重新寻找第八个皇后的位置
                                一旦第八个皇后的位置确定，就打印map
                                即map[i] = k;
                           */

                    }
                    /*如果冲突，即第i行的皇后不能放在当前这列
                        就继续执行 map[i] = k;
                        即继续将第n个皇后（当前行的皇后）放到下一列，继续尝试
                        即将第n个皇后，放置在本行的后移一个列的位置
                     */
                }
            }

    }

    /**
     * 当放置第n个皇后时，判断该皇后是否和前面已经摆放 的皇后冲突（在同一列，或同一斜线）
     * 判断这个点是否能够放置皇后
     * @param n 假设第n个皇后所在行--> map[n]就是第n个皇后所在的列
     * @return
     */
    public static boolean judge(int n){
        for (int i = 0; i < n; i++) {
            if(map[i] == map[n]){
//                第n个皇后的列标和之前任一皇后的列标重复
                return false;
            }else if(Math.abs(map[n] - map[i]) == Math.abs(n-i)){
                /*第n个皇后和之前任一皇后在同一斜线
                    行坐标差值的绝对值 == 列坐标差值的绝对值
                 */
                return false;
            }
        }
        return true;
    }

    private static void printQueens(){
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                if(map[i] == j + 1){
                    System.out.print(map[i]+"\t");
                }else{
                    System.out.print(" "+"\t");
                }
            }
            System.out.println();
        }
    }
}
